1. Technical Field
Embodiments of the present invention relate generally to shared resource access and more particularly to a method and system for providing access to a shared resource within a data processing system utilizing selective locking.
2. Description of the Related Art
As data processing systems have become more pervasive and complex, utilization of shared resources (i.e., resources which are commonly visible, accessible, useable, or the like among data processing systems and/or components thereof) has increased. Shared resources may be utilized to enable communication among systems or system elements, reduce and/or distribute data processing system component costs, and/or to increase the speed with which data processing may be performed. Shared resources are particularly useful in data processing systems comprising multiple processing elements operating in parallel.
A processing element is a data processing system component which may be implemented in hardware (e.g., as a general or special-purpose processor or processor core, a programmable logic device, or the like), firmware, software, or a combination thereof. Software processing elements may include any of a number of components such as processes or threads within a multithreading data processing system. In such a multithreading system, each application is partitioned among one or more processes with each process being associated with an address space, such that different processes can operate concurrently without resource conflicts. Each process in turn includes one or more threads of control, or “threads.” A thread is a unit or path of execution within an associated or “parent” process. Each process' threads share a common address space, thus simplifying inter-thread communication and reducing context switch time between threads as compared to that between processes or applications.
While providing a number of benefits, sharing a resource among multiple processing elements may present a number of challenges. Coordination of access to a shared resource to ensure consistency of the resource's state and to avoid data processing system exceptions (e.g., faults, traps, aborts, or the like) is one such challenge prevalent with modern data processing systems. Processing element synchronization is particularly important among threads of a multithreading data processing system as such processing elements may operate effectively simultaneously with one another and be stopped or started at any time during operation. Such simultaneous operation and intermittent blocking may lead to unstable execution (e.g., livelock, deadlock, or the like).
Consequently, conventional multithreaded programming strives to make execution sequences (e.g., routines, functions, procedures, stubs, or the like) which are “thread-safe” and reentrant utilizing programming techniques and thread synchronization tools. A synchronization tool may include any logical or physical element used to coordinate or synchronize the operation of two or more processing elements. In the multithreading data processing system context, such synchronization tools may include interlocked functions, critical sections, synchronization kernel objects (e.g., mutual exclusion objects (mutexes) and semaphores), events, or the like.
One exemplary shared resource which has presented particular difficulty in the multithreading data processing system context is the list data structure (e.g., a singly-linked list, queue, stack, or the like). A typical list data structure (e.g., a stack) includes a head pointer or reference indicating the first element or “node” of the list. Each element of the list in turn includes a pointer or reference to the next element such that, using the head pointer or “anchor” all elements of the list may be accessed sequentially. A list element may be removed utilizing a conventional execution sequence in which a reference to the first list element is associated, via a first load operation, with a first variable, a reference to the second list element is associated, via a second load operation utilizing the reference to the first list element, with a second variable, and the first list element is then re-identified within the second list element via a store operation of the second variable's reference value.
In a multithreading data processing system environment, the above-described technique for list element removal suffers from a number of shortcomings. For example, where separate threads are utilized to perform the element removal execution sequence and a corresponding element addition sequence or routine, the list data structure may become corrupted. To avoid such list corruption, multithreading data processing systems have more-recently begun providing interlocked function-type synchronization tools. For example, the linked “load and reserve” (LAR) and “store conditional” (STC) instructions provided as part of the PowerPC™ Processor Architecture by International Business Machines Corporation of Armonk, N.Y., allow a value or variable to be atomically manipulated without requiring a prohibitive amount of time or system resources. By supplanting the first load operation and store operation described above with LAR and STC instructions, respectively, a race condition and possible system error may be avoided in most circumstances.
While avoiding the corruption of an associated list data structure, the use of such interlocked (e.g., LAR and STC) functions does not preclude all system exceptions. For example, freed or “reclaimed” storage (e.g., system memory) may be dereferenced in a scenario where two distinct threads perform the above-described element removal execution sequence including interlocked functions. A first thread and a second thread may both obtain a pointer or reference to the first list element, via a LAR operation. Thereafter, the first thread may complete the element removal execution sequence and free storage associated with the removed list element. When the second thread subsequently attempts to dereference the obtained pointer, an exception (e.g., a page fault) may occur, disabling the data processing system within which the threads exist.
To avoid the occurrence of data processing system exceptions brought on by multithreaded programming, a global lock synchronization tool may be used. Serialization of list data structure operations using a global lock is frequently too burdensome however, potentially causing memory delay, path length, and concurrency penalties. Such a burden is frequently prohibitive, particularly since the frequency with which a removed list item's associated storage is reclaimed is relatively small compared to the total number of list operations typically performed.